#pragma once
#include <iostream>
#include <time.h>
#include <mutex>
#include <vector>
#include <string>
#include <algorithm>
#include <assert.h>
#include <thread>
// 包含公共的头文件的定义
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024; // C++中尽量不要用宏
static const size_t NFREELIST = 208; // 自由链表中桶的总数量

// 条件编译
// _WIN32在32和64位下都有定义，_WIN64只在64位下有定义，32下并无定义，所以要_WIN64在前
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	// linux...
#endif



// 取头上的4/8个字节
static void*& NextObj(void* obj) // 加static只在当前文件可见
{
	return *(void**)obj;
}

// 管理切分好的小对象的自由链表 （类似于多个定长内存池）
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);

		// 头插：
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;
	}

	// Push只插入一个，PushRange给一个范围直接插入多个
	void PushRange(void* start, void* end)
	{
		NextObj(end) = _freeList; // 理论上该位置没有内存对象了
		_freeList = start;
	}

	void* Pop()
	{
		assert(_freeList);

		// 头删：
		void* obj = _freeList;
		_freeList = NextObj(obj);

		return obj;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
};


// 计算对象大小的对齐映射规则
// 至少要8byte对齐，因为在64位下得要8byte才能存的下下一个对象的指针
class SizeClass
{
public:
	// 不同的范围段按不同的值去对齐，浪费的内碎片控制在10%
	// 整体控制在最多10%左右的内碎片浪费 （后面为桶的数量，1 ~ 128 8byte对齐需16个桶）
	// [1,128]					8byte对齐		freelist[0, 16)
	// [128+1,1024]             16byte对齐		freelist[16, 72)
	// [1024+1,8*1024]          128byte对齐		freelist[72, 128)
	// [8*1024+1,64*1024]       1024byte对齐		freelist[128, 184)
	// [64*1024+1,256*1024]     8*1024byte对齐	freelist[184, 208)
	

	// 普通版本
	//size_t _RoundUp(size_t size, size_t alignNum) // 子函数，帮助计算
	//{
	//	// 进行对齐
	//	size_t alignSize; // 进行对齐后的字节数
	//	if (size % alignNum != 0)
	//	{
	//		alignSize = (size / alignNum + 1) * alignNum;
	//	}
	//	else
	//	{
	//		alignSize = size;
	//	}
	//	return alignSize;
	//}

	// 高级版本：
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		// 有点类似于IP同一网段的的思想，保持低N位的值为0
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}


	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8); // 按照对齐数进行对齐返回
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			// 当size大于256k时证明出现了点问题，正常不会大于256
			assert(false);
			return -1;
		}
	}

	// 普通版本：计算是在几号桶
	//static inline size_t _Index(size_t bytes, size_t alignNum)
	//{
	//	if (bytes % alignNum == 0)
	//	{
	//		return bytes % alignNum - 1; // 0号下标情况
	//	}
	//	else
	//	{
	//		return bytes / alignNum; // 非零号下标可以直接除就能得出在几号桶
	//	}
	//}

	// 高级版本
	// 假设1 ~ 8：1 + 
	static inline size_t _Index(size_t bytes, size_t align_shift) // align_shift：对齐数的次方
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}


	// 计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3); // 小于128按8对齐，2^3 = 8
		}
		else if (bytes <= 1024) {
			
			// 按N字节对齐，其数要减去上N字节对齐的对齐数,例如: bytes - 128
			return _Index(bytes - 128, 4) + group_array[0]; 
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1]
				+ group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

	// 一次thread cache 从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		// [2, 512],一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 大对象一次批量上限低
		int num = MAX_BYTES / size; // MAX_BYTES 自定义宏 256k
		if (num < 2)
			num = 2;

		if (num < 512)
			num = 512;

		// 就是折中取值，折中的算出来是多少就给多少，超过512就只给512，只有一个的至少给两个

		return num;
	}

};

// 管理多个连续页大块内存跨度结构
struct Span
{
	// size_t在32位下是可行的，但是64位下是不行的，size_t = unsigned int
	// 64位下要使用 unsigned long long
	PAGE_ID _pageId = 0;		// 大块内存起始页的页号
	size_t _n = 0;				// 页的数量

	// Span为一个带头双向循环的链表：
	Span* _next = nullptr;		// 双向链表的结构
	Span* _prev = nullptr;

	size_t _useCount = 0;		// 切好的小块内存，被分配给thread cache的计数
	void* _freeList = nullptr;	// 切好的小块内存的自由链表
};

// 带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);
		
		Span* prev = pos->_prev;
		// prev newspan pos
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head); // 不能删除哨兵位节点

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;

		// 并不需要把pos给delete掉，因为这个Span要给给下一层的page cache
	}

private:
	Span* _head;
public:
	std::mutex _mtx; // 桶锁
};